// prim
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e2 + 7;

int n;
int dis[maxn];      // 距离
int vis[maxn];      // 访问标记
int e[maxn][maxn];  // 邻接矩阵存图

int Prim() {
    int ans = 0;
    for (int i = 0; i <= n; ++i) dis[i] = 2e9, vis[i] = 0;  //初始化
    dis[1] = 0;  // prim算法任选起点，于是可以选择1为起点
    for (int i = 1; i <= n; ++i) {
        int u = 0;  //注意dis[0]已经初始化为无穷大了，不用管了
        for (int j = 1; j <= n; ++j)
            if (!vis[j]) {
                if (dis[j] < dis[u]) u = j;
            }
        vis[u] = 1;
        ans += dis[u];  //更新答案啦
        for (int j = 1; j <= n; ++j)
            if (!vis[j]) {  //拿u点来更新新拓展的边
                if (dis[j] > e[u][j]) dis[j] = e[u][j];
            }
    }
    return ans;
}

void solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) scanf("%d", &e[i][j]);
    printf("%d\n", Prim());
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
}